1. Field:
The present invention relates to a parallel program, and more specifically, relates to a method and system of deadlock detection in a parallel program.
2. Description of the Related Art
Process (thread) deadlock in a parallel program is a very fatal problem. Process (thread) deadlock refers to a phenomenon in which two or more processes (threads) wait for each other due to contention for a shared resource during operation thereof, and unless a process (thread) in a deadlock gives up the shared resource, the two transactions in the deadlock will wait indefinitely. Process (thread) deadlock generally will result in paralysis of the entire system. There are many factors triggering process (thread) deadlock, mainly comprising: (1) limited system resources; (2) an unsuitable order of advancing the operation of the processes (threads); and (3) inappropriate resource distribution. If the system has sufficient resources, the resource request from each process can be satisfied, and possibility of an occurrence of the deadlock is very low; otherwise, the process will get into a deadlock due to contention for limited resources. Secondly, if the order of advancing the operation of the processes is different from the speed thereof, a deadlock may occur. In order to avoid heavy damages to the entire system caused by process (thread) deadlock and to improve stability of the system, an effective method of deadlock detection is needed so as to find a process (thread) deadlock in time and take suitable measures for releasing from the deadlock, thereby avoiding further deterioration of the operating situation of the system.
The problem of deadlock detection is resolved generally based on deadlock detection algorithms in graph theory, which constructs a graph visually representative of the situation in a deadlock, e.g. a lock graph and a resource distribution graph, by recording lock events during operation of the parallel program. In the graph, a node represents a lock of a resource, and a directed edge from one node to another node represents that a process that has acquired the lock of one resource is requesting to acquire the lock of another resource. If directed edges between two or more nodes in the graph form a closed directed loop, this indicates that there is a deadlock in the parallel program, and therefore the deadlock can be detected by checking if there is a directed loop in the graph.
When assessing the performance of a deadlock detection algorithm, pseudo-deadlock rate is regarded as an important index. In the actual applications, if the pseudo-deadlock rate is excessively high, a lot of time and energy of the testers are often consumed for finding a true deadlock, so it is extremely important for deadlock detection to reduce the pseudo-deadlock rate. At present, research is conducted for improving the algorithms to reduce the pseudo-deadlock rate, but the improvements of the algorithms in theory do not have universality in the actual applications. Even if adopting the same algorithm, adaptive adjustment shall be made to the algorithm with respect to specific application environments and products, which requires the testers and developers to know the kernel of the algorithm very much such that it is possible for them to modify the codes of the algorithm directed to different environments. However, in actual applications, there exist great risks for the modifications to the kernel of the algorithm, and moreover, it is bad for the transplantation of the codes for the algorithm. Therefore, an improved deadlock detection method is needed, which can be applied with facility to various development environments, and can improve the accuracy of deadlock detection without depending on the deadlock detection algorithm per se and reduce the development costs.